package com.zsj.Recursion;

/**
 * @Author zsj
 * @Version 1.0
 * @Date 2023/11/4 14:07
 * @Description 斐波那契数列
 */
public class Fibonacci {

    public static void main(String[] args) {
//        System.out.println(n--);
        //递归的复杂度是一个常数 根据递归调用的次数
        //递归调用次数的公式是 2*f(n)-1
        System.out.println(System.currentTimeMillis());
        System.out.println(getIndex(7));
        System.out.println("================");
        // 调用数学公司的时间复杂度是  (1.618的n次方)
        System.out.println(System.currentTimeMillis());
        System.out.println("================");
        System.out.println(math(7));
        System.out.println(System.currentTimeMillis());
        System.out.println("================");
        //记忆法也是O(n)的复杂度 但是空间开销更大一些
        System.out.println(arr(7));
        System.out.println(System.currentTimeMillis());
        System.out.println("================");
        //dp使用空间换时间 O(n)复杂度
        System.out.println(dp(7));
        System.out.println(System.currentTimeMillis());
    }

    private static int getIndex(int n) {
        return r(n);
    }

    private static int r(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return r(n - 1) + r(n - 2);
    }

    private static int arr(int n) {
        int[] arr = new int[n + 1];
        arr[0] = 0;
        arr[1] = 1;
        int res = 0;
        for (int i = 2; i < arr.length; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
            res = arr[i];
        }
        return res;
    }

    private static int dp(int n) {
        int a = 0;
        int b = 1;
        int res = 0;
        while (--n != 0) {
            res = a + b;
            a = b;
            b = res;
        }
        return res;
    }

    private static int math(int n) {
        double sqrt5 = Math.sqrt(5);
        double f_phi = Math.pow((1 + sqrt5) / 2, n);
        double phi = Math.pow((1 - sqrt5) / 2, n);
        return (int) Math.round((f_phi - phi) / sqrt5);
    }
}
